//https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
class Solution {
    int ret;
    int[] dx = { 1, -1, 0, 0 };
    int[] dy = { 0, 0, 1, -1 };
    int m, n;
    boolean[][] check;

    public int wardrobeFinishing(int m_, int n_, int cnt) {
        m = m_;
        n = n_;
        check = new boolean[m][n];
        dfs(0, 0, cnt);
        return ret;
    }

    public void dfs(int i, int j, int cnt) {
        check[i][j] = true;
        ret++;
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && isRight(x, y, cnt)) {
                dfs(x, y, cnt);
            }
        }
    }

    public boolean isRight(int x, int y, int cnt) {
        int sum = 0;
        while (x != 0) {
            sum += x % 10;
            x /= 10;
        }
        while (y != 0) {
            sum += y % 10;
            y /= 10;
        }
        return sum <= cnt;
    }
}